Soldados de Conway

El problema de los soldados de Conway o el problema de las damas (en referencia al juego de mesa) es un juego matemático para una persona que fue desarrollado y analizado por el matemático John Horton Conway en 1961. Es una variante del solitario senku que se realiza en un tablero infinito. El tablero se divide por una línea horizontal que se extiende de forma indefinida, sobre la cual aparecen celdas vacías y en la parte inferior una cantidad arbitraria de piezas o soldados, una por casilla. Al igual que en el juego de damas, los movimientos consisten en que una pieza brinque sobre otra pieza adyacente, ya sea vertical u horizontalmente (pero no en diagonal) y "capturándola" (eliminándola del tablero) en el proceso. El objetivo del juego es llevar a un soldado por encima y tan lejos de la línea horizontal como sea posible.

Arreglos de soldados de Conway necesarios para alcanzar las filas 1, 2, 3 y 4. Las posiciones marcadas con B son alternativas a las posiciones marcadas con A.

Conway demostró, que independientemente de la estrategia usada, no existe una serie de movimientos que permitan a un soldado avanzar más de cuatro filas por encima de la línea horizontal. El argumento de la prueba involucra la asignación de coeficientes a las casillas de una forma muy particular (y relacionada con la proporción áurea) de tal manera que la suma de los coeficientes asignados a todas las fichas del tablero no pueda ser incrementada por ningún movimiento permisible. Este argumento ha sido presentado en diversos libros de matemática popular.

Simon Tatham y Gareth Taylor han demostrado que es posible alcanzar la quinta fila mediante una cantidad infinita de movimientos, mismo resultado que aparece también en un artículo de Pieter Blue y Stephen Hartke.

Cuando se permiten saltos en diagonal, es posible llevar a los soldados hasta la octava fila (pero no hasta la novena). Se ha demostrado también que, en la versión n-dimensional del juego, la máxima fila que se puede alcanzar es 3n-2. El argumento de Conway demuestra que la fila 3n-1 no es alcanzable aunque es considerablemente más complicado demostrar que sí es posible llegar a la fila 3n-2, como demuestran en el artículo de Eriksson y Lindstrom.

Prueba de que la quinta fila es inaccesible

Notación y definiciones

Podemos suponer que las casillas corresponden a puntos del plano cartesiano con coordenadas enteras, que los soldados están inicialmente en casillas cuya ordenadas (coordenada y) no son positivas y sin pérdida de generalidad podemos asumir que la casilla objetivo está en las coordenadas (0,5).

A cada punto de coordenadas enteras ocupado por un soldado le asignamos el valor $x^{n}$ donde n es la distancia de ese punto a la casilla objetivo en la métrica del taxi y

$x={\frac {{\sqrt {5}}-1}{2}}$.

Consideramos entonces la suma S de todos los términos que corresponden a posiciones ocupadas. En el caso de que hubiese una cantidad infinita de posiciones ocupadas, procederemos a usar series en vez de sumas.

Cálculos correspondientes a los movimientos

La selección de

$x={\frac {{\sqrt {5}}-1}{2}}$,

se realiza con el objetivo de que se cumpla la relación

$x^{2}+x-1=0$

y por ende

$x^{r}+x^{r-1}-x^{r-2}=0$ para cualquier valor entero de r

es decir:

$x^{r-2}=x^{r}+x^{r-1}$ para cualquier valor entero de r.

Si al realizar un salto, el soldado se aleja de la casilla objetivo, si su posición tenía originalmente el valor $x^{r}$, su nuevo valor será $x^{r+2}$ pero tanto su posición original ($x^{r}$) como la casilla sobre la que brincó ($x^{r+1}$) quedan vacías de manera que la suma total del tablero cambia por

$x^{r+2}-x^{r+1}-x^{r}=x^{r+2}-x^{r-2}$

y al ser $x<1$ dicho cambio es negativo por lo que la suma de todo el tablero disminuye.

Por otro lado, si al realizar un salto el soldado se acerca a la casilla objetivo, partiendo desde una posición con valor $x^{r}$, el cambio de la suma total sería

$x^{r-2}-x^{r-1}-x^{r}=0$,

en otras palabras, la suma total del tablero permanece sin cambio.

Demostración de la imposibilidad

Es posible demostrar, usando series convergentes, junto a la propiedad $x^{2}=1-x$, que si todas las casillas con coordenadas y negativas o cero estuvieran ocupadas, la suma total del tablero sería igual a 1, y por tanto cualquier configuración finita tiene una suma total estrictamente menor que 1.

Por otra parte, mencionamos arriba que cualquier movimiento hace que la suma total se mantenga igual o disminuya, pero nunca aumente.

Finalmente, si tras una serie finita de movimientos algún soldado llegase a la casilla que corresponde al punto (0,5), el valor que tendría asignado sería $x^{0}=1$ y por tanto que la suma de todo el tablero debe ser mayor de 1.

Lo anterior es una contradicción, puesto que ningún movimiento puede hacer que la suma total aumente y por tanto nunca puede exceder su valor inicial igual a uno.

La conclusión es, entonces, que no es posible que un soldado llegue a la casilla correspondiente al (5,0), es decir, un soldado nunca puede avanzar cinco filas hacia arriba.

Referencias

• E. Berlekamp, J. Conway and R. Guy, Winning Ways for your Mathematical Plays, 2nd ed., Vol. 4, Chap. 23: 803—841, A K Peters, Wellesley, MA, 2004.
• R. Honsberger, A problem in checker jumping, in Mathematical Gems II, Chap. 3: 23—28, MAA, 1976.
• H. Eriksson and B. Lindstrom, Twin jumping checkers in Z_d, Europ. J. Combinatorics, 16 (1995), 153–157.

Enlaces externos

• cut-the-knot.org explains the game
• A page describing several variations of the game, with recent references
• Weisstein, Eric W. «Conway's Soldiers». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Plus online magazine describes the game
• A video game based on Conway's Soldiers
• Tatham and Taylor's paper
• mathproblems.info (search for #15 Checker problem)
• A solution to the fifth row using infinite moves

• Datos: Q5015732
• Multimedia: Conway's Soldiers / Q5015732